package com.leetcode.math;

import com.leetcode.annotation.Remark;

import java.util.HashSet;
import java.util.PriorityQueue;

/**
 * 面试题 17.09. 第 k 个数
 * 有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。
 * 例如，前几个数按顺序应该是 1，3，5，7，9，15，21。
 * <p>
 * 示例 1:
 * <p>
 * 输入: k = 5
 * <p>
 * 输出: 9
 * <p>
 * https://leetcode.cn/problems/get-kth-magic-number-lcci/
 */
@Remark("动态规划 - 第k个数")
public class M_getKthMagicNumber {

    public static void main(String[] args) {
        System.out.println(getKthMagicNumber(11));
    }

    public static int getKthMagicNumber(int k) {
        // 1,3,5,7, 9,15,21, 25,27,35,45, 49, 63,
        // 1、最小堆，O(klogk)
        // return minDump(k);


        // 2、动态规划，O(k)
        // min(dp[i]*3,dp[i]*5,dp[i]*7)
        int[] dp = new int[k];

        dp[0] = 1;
        int index_dp3 = 0, index_dp5 = 0, index_dp7 = 0;

        for (int i = 1; i < k; i++) {
            int dp3 = dp[index_dp3] * 3, dp5 = dp[index_dp5] * 5, dp7 = dp[index_dp7] * 7;
            dp[i] = Math.min(Math.min(dp3, dp5), dp7);
            if (dp[i] == dp3) {
                index_dp3++;
            }
            if (dp[i] == dp5) {
                index_dp5++;
            }
            if (dp[i] == dp7) {
                index_dp7++;
            }
        }
        return dp[k - 1];


    }

    private static int minDump(int k) {
        /**
         * 方法一：最小堆
         * 要得到从小到大的第 kk 个数，可以使用最小堆实现。
         *
         * 初始时堆为空。首先将最小的数 11 加入堆。
         *
         * 每次取出堆顶元素 xx，则 xx 是堆中最小的数，由于 3x, 5x, 7x3x,5x,7x 也是符合要求的数，因此将 3x, 5x, 7x3x,5x,7x 加入堆。
         *
         * 上述做法会导致堆中出现重复元素的情况。为了避免重复元素，可以使用哈希集合去重，避免相同元素多次加入堆。
         *
         * 在排除重复元素的情况下，第 kk 次从最小堆中取出的元素即为第 kk 个数。
         *
         * 作者：LeetCode-Solution
         * 链接：https://leetcode.cn/problems/get-kth-magic-number-lcci/solution/di-k-ge-shu-by-leetcode-solution-vzp7/
         * 来源：力扣（LeetCode）
         * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
         */

        // 最小堆
        int[] factories = new int[]{3, 5, 7};
        PriorityQueue<Integer> minDumpQueue = new PriorityQueue<>();
        // 去重，不用添加到最小堆里面
        HashSet<Integer> set = new HashSet<>();
        set.add(1);
        minDumpQueue.offer(1);

        int min = 1;

        for (int i = 0; i < k; i++) {
            min = minDumpQueue.poll();
            for (int j = 0; j < factories.length; j++) {
                int dumpQueue = min * factories[j];
                if (!set.contains(dumpQueue)) {
                    minDumpQueue.offer(dumpQueue);
                }
                set.add(dumpQueue);
            }
        }
        return min;
    }
}
